UVa/10482 - The candyman can/10482.2.cpp

   1 /*
   2   Problem: 10482 - The Candyman can
   3   (UVa Online Judge)
   4
   5   Andrés Mejía-Posada
   6
   7   ¡Accepted!
   8  */
   9 #include <iostream>
  10 #include <vector>
  11 #include <algorithm>
  12 using namespace std;
  13
  14 const int SIZE = 52, MAXN = 32;
  15
  16 /*
  17   dp[i][a][b] = verdadero si puedo repartir las primeras
  18   i monedas en tres grupos tales que el grupo con mayor peso
  19   tenga a unidades más que el grupo con menos peso & el grupo
  20   de la mitad tenga b unidades más que el grupo con menos peso
  21  */
  22 bool dp[MAXN][SIZE+1][SIZE+1];
  23
  24 int main(){
  25   int Casos;
  26   cin >> Casos;
  27   for (int C=1; C<=Casos; C++){
  28     int n, sum = 0;
  29     cin >> n;
  30     vector<int> w(n);
  31     for (int i=0; i<n; ++i){
  32       cin >> w[i];
  33       sum += w[i];
  34     }
  35
  36     sum = min(sum, SIZE);
  37
  38     for (int i=0; i<n; ++i)
  39       for (int a=0; a<=sum; ++a)
  40         for (int b=0; b<=sum; ++b)
  41           dp[i][a][b] = false;
  42
  43     cout << "Case " << C << ": ";
  44     //cout << "Sum: " << sum << endl;
  45
  46
  47     dp[0][w[0]][0] = true;
  48     for (int i=0; i<n-1; ++i)
  49       for (int a=0; a<=sum; ++a)
  50         for (int b=0; b<=sum; ++b)
  51           if (dp[i][a][b])
  52             //Intento agregar el confite i+1-ésimo a los tres grupos
  53             //teniendo en cuenta las nuevas diferencias que puedan formarse
  54             //por ejemplo, al agregar un confite muy pesado al grupo con menos peso
  55             //este podría convertirse en el grupo con más peso, asi que hay que sacar las diferencias
  56             for (int j=0; j<3; ++j){
  57               vector<int> t(3);
  58               t[0] = a, t[1] = b, t[2] = 0;
  59               t[j] += w[i+1];
  60               sort(t.begin(), t.end());
  61               if (t[2] - t[0] <= sum && t[1] - t[0] <= sum){
  62                 dp[i+1][t[2] - t[0]][t[1] - t[0]] = true;
  63                 //printf("\ndp[%d][%d][%d] -> dp[%d][%d][%d] = true", i, a, b, i+1, t[2]-t[0], t[1]-t[0]);
  64               }
  65             }
  66
  67     /*
  68     cout << endl;
  69     for (int i=0; i<n; ++i){
  70       cout << "Usando las primeras " << i << " monedas: " << endl;
  71       for (int a=0; a<=sum; ++a){
  72         for (int b=0; b<=sum; ++b){
  73           cout << dp[i][a][b] << " ";
  74         }
  75         cout << endl;
  76       }
  77     }
  78     */
  79
  80     int answer = -1;
  81     for (int a=0; a<=sum && answer == -1; ++a)
  82       for (int b=0; b<=a && answer == -1; ++b)
  83         if (dp[n-1][a][b]){
  84           answer = a;
  85           //cout << "b es : " << b << endl;
  86         }
  87
  88     cout << answer << endl;
  89
  90   }
  91   return 0;
  92 }
  93
  94